#include <stdio.h>

// 插入排序函数
// 参数说明：
//   arr[]：待排序的数组
//   n：数组的长度
void insertionSort(int arr[], int n) {
    int i, key, j;

    // 外层循环：从第二个元素开始遍历（索引1），逐个处理每个待插入元素
    for (i = 1; i < n; i++) {
        key = arr[i];  // 当前需要插入的元素（类似于抓牌动作）
        j = i - 1;     // 从当前元素的前一个位置开始比较

        // 内层循环：寻找key的插入位置
        // 条件1：j >= 0 防止越界
        // 条件2：arr[j] > key 寻找比key小的元素的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 将比key大的元素后移一位（腾出空位）
            j = j - 1;            // 向左继续比较
        }

        // 循环结束时，j的位置是第一个比key小的元素，因此插入位置是j+1
        arr[j + 1] = key;  // 将key插入到正确位置（类似插入到已排序的手牌中）
    }
}

// 打印数组的辅助函数
// 参数说明：
//   arr[]：需要打印的数组
//   n：数组的长度
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);  // 逐个打印元素，用空格分隔
    }
    printf("\n");  // 换行
}

int main() {
    // 测试数组
    int arr[] = { 12, 11, 13, 5, 6 };

    // 计算数组长度：总字节数 / 单个元素的字节数
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, n);  // 打印排序前数组

    insertionSort(arr, n);  // 调用排序函数

    printf("排序后的数组：\n");
    printArray(arr, n);  // 打印排序结果

    return 0;  // 程序正常退出
}